Merge Intervals || Wiggle Sort II

发表于

Merge Intervals

Question

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

Analysis

利用Collections.sort 重写Compare函数对Interval内区间进行排序，排序的原则是以start，end进行升序排序，排序后进行区间的合并。

  • end记录可合并区间的最大上界，start记录下界
  • 当前区间不可合并时，将区间[start,end]加入结果
  • 在循环结束后，将最后一个区间加入结果

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res=new ArrayList<Interval>();
        if(intervals.size()<=1) return intervals;
        Collections.sort(intervals, new Comparator<Interval>(){
          public int compare(Interval i1, Interval i2){
              if(i1.start!=i2.start){
                  return i1.start-i2.start;
              }
              return i1.end-i2.end;
          }  
        });
        
        int start=intervals.get(0).start;
        int end=intervals.get(0).end;
        for(Interval tmp:intervals){
            if(tmp.start<=end){
                end=Math.max(end,tmp.end);
            }else{
                res.add(new Interval(start,end));
                start=tmp.start;
                end=tmp.end;
            }
        }
        
        res.add(new Interval(start,end));
        return res;
    }
}

Wiggle Sort II

Question

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example:

(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].

(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:

You may assume all input has valid answer.

Analysis

O(n)/O(nlogn)+O(n) 解法

将原本的无序数组排序，从中位数mid分为前后两半部分，依次交替从前半部分和后半部分倒序选元素加入结果数组，前半部分的元素位于脚标为偶数的位置，后半部分的元素位于脚标为奇数的位置

O(n)+O(1)解法

LeetCode Discussion

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        
        int[] tmp=new int[nums.length];
        int mid=(nums.length+1)>>1;
        int right=nums.length;
        
        for(int i=0;i<nums.length;i++){
            tmp[i]= (i&1)==0?nums[--mid]:nums[--right];
        }
        
        for(int i=0;i<nums.length;i++){
            nums[i]=tmp[i];
        }
    }
}